package awk.algorithm;

/**
 * created with IDEA
 *
 * @author haifeng.wang
 * @since 2019-11-11-23:43
 */
public class MaxSum {

	public static void main(String[] args) {
		int[] arr = {-1, 4, -6, 1, -9};

		maxSum(arr);
	}

	/**
	 * 时间复杂度O（N * N）空间复杂度O（1）） 求出所有的子数组的和，比较选择出最大值。利用双重循环就可以遍历到所有的子数组。
	 *
	 * @param arr
	 */
	public static void maxSum1(int[] arr) {
		int max = 0, sum;
		for (int i = 0; i < arr.length; i++) {
			sum = 0;
			for (int j = i; j < arr.length; j++) {
				//遍历数组的所有子数组，并将子数组的最大和保存在max中。
				sum += arr[j];
				max = Math.max(max, sum);
				//max保存最大的子数组的和
			}
		}
		System.out.println(max);
	}

	/**
	 * 解法2（动态规划时间复杂度O（N）空间复杂度O（1））
	 * 遍历数组，用 sum 保存子数组的和，当 sum<0 时 将 arr[i] 赋值给 sum，用 max 保存最大值。
	 *
	 * @param arr
	 */
	public static void maxSum(int[] arr) {
		int max = 0, sum = 0;
		for (int i = 0; i < arr.length; i++) {
			if (sum <= 0) {
				sum = arr[i];
				//如果 sum<0 重新赋值
			} else {
				sum += arr[i];
			}
			max = Math.max(sum, max);
			//将最大值保存在max中。
		}
		System.out.println(max);
	}
}
